package concurrensy.sorter;

import java.util.ArrayList;
import java.util.List;

public class ConcurrencyMergeSorter<T extends Comparable<T>> implements
		MergeSorter<T> {

	private class Sorter implements Runnable {

		List<T> list;

		@Override
		public void run() {
			sort(list);
		}

		Sorter(List<T> list) {
			this.list = list;
		}
	}
	
	private static final int VALUES_FOR_ONE_THRAD = 1000;

	@Override
	public List<T> mergeSort(List<T> listToSort) {
		List<T> result = new ArrayList<>();
		List<T> leftList = new ArrayList<>(listToSort.subList(0,
				listToSort.size() / 2));
		List<T> rightList = new ArrayList<>(listToSort.subList(listToSort.size() / 2,
				listToSort.size()));
		if (listToSort.size() > VALUES_FOR_ONE_THRAD) {
			List<T> leftSortedList = mergeSort(leftList);
			List<T> rightSortedList = mergeSort(rightList);
			result = merge(leftSortedList, rightSortedList);
		} else {
			Thread leftSorter = new Thread(new Sorter(leftList));
			leftSorter.start();
			sort(rightList);
			try {
				leftSorter.join();
			} catch (InterruptedException e) {
				e.printStackTrace();
			}
			result = merge(leftList, rightList);
		}
		return result;
	}

	private List<T> merge(List<T> leftList, List<T> rightList) {
		List<T> result = new ArrayList<>();
		while ((!leftList.isEmpty()) && (!rightList.isEmpty())) {
			if (leftList.get(0).compareTo(rightList.get(0)) < 0) {
				result.add(leftList.get(0));
				leftList.remove(0);
			} else if (leftList.get(0).compareTo(rightList.get(0)) == 0) {
				result.add(leftList.get(0));
				result.add(rightList.get(0));
				leftList.remove(0);
				rightList.remove(0);
			} else {
				result.add(rightList.get(0));
				rightList.remove(0);
			}
		}
		while ((!leftList.isEmpty())) {
			result.addAll(leftList);
			leftList.clear();
		}
		while ((!rightList.isEmpty())) {
			result.addAll(rightList);
			rightList.clear();
		}
		return result;
	}

	private void sort(List<T> list) {
		for (int count = list.size() - 1; count > 0; count--) {
			for (int i = 0; i < count; i++) {
				if (list.get(i).compareTo(list.get(i + 1)) > 0) {
					swap(list, i, i + 1);
				}
			}
		}
	}

	private void swap(List<T> list, int el1, int el2) {
		T temp1 = list.get(el1);
		T temp2 = list.get(el2);
		list.remove(el1);
		list.add(el1, temp2);
		list.remove(el2);
		list.add(el2, temp1);
	}

}
